package 极客算法训练营.chapter09;

import java.util.Arrays;

public class 最小基因变化 {

    class Solution {
        private int result = Integer.MAX_VALUE;
        public int minMutation(String start, String end, String[] bank) {
            //准备数据
            char[] _start = start.toCharArray();
            char[] _end = end.toCharArray();
            char[][] banks = new char[bank.length][8];//基因是8序列
            for (int i = 0; i < banks.length; i++) {
                banks[i] = bank[i].toCharArray();
            }
            dfs(_start, _end, banks, 0);
            return result == Integer.MAX_VALUE ? - 1 : result;
        }

        public void dfs(char[] start, char[] end, char[][] banks, int changes) {
            //终止条件
            if (Arrays.equals(start, end)) {
                result = Math.min(changes, result);
                return;
            }
            for (int i = 0; i < banks.length; i++) {
                char[] bank_copy = banks[i];
                if (bank_copy == null) continue;
                int diff = 0;
                for (int j = 0; j < bank_copy.length; j++) {
                    if (start[j] != bank_copy[j]) {
                        diff++;
                    }
                }
                if (diff == 1) {
                    banks[i] = null;
                    dfs(bank_copy, end, banks, changes + 1);
                    banks[i] = bank_copy;
                }
            }
        }
    }
}
